package A1_回溯;

public class LC_37解数独 {
    public void solveSudoku(char[][] board) {
        backtracking(board);
    }
    public boolean backtracking(char[][] board){
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board.length;j++){
                if(board[i][j]!='.')
                    continue;
                for(char k='1';k<='9';k++){//此处是小于等于
                    if(isvalid(i,j,k,board)){
                        board[i][j]=k;
                        boolean result=backtracking(board);
                        if(result==true)
                            return true;
                        board[i][j]='.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    public boolean isvalid(int row,int col,int k,char[][] board){
        //列
        for(int i=0; i<board.length;i++){
            if(board[i][col]==k)
                return false;
        }
        //行
        for(int i=0; i<board.length;i++){
            if(board[row][i]==k)
                return false;
        }
        //3x3
        int start=(row/3)*3;
        int end=(col/3)*3;
        for(int i=start;i<start+3;i++){
            for(int j=end;j<end+3;j++){
                if(board[i][j]==k)
                    return false;
            }
        }
        return true;
    }
}
